SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Graph-structured stack</title>

</head>

Graph-structured stack

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Computer_science" title="Computer science">computer science</a>, a graph-structured stack (GSS) is a <a href="Directed_acyclic_graph" title="Directed acyclic graph">directed acyclic graph</a> where each directed <a href="Path_(graph_theory)" title="Path (graph theory)">path</a> represents a <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a>.

The graph-structured stack is an essential part of <a href="GLR_parser" title="GLR parser">Tomita's algorithm</a>, where it replaces the usual <a href="Stack_(data_structure)" class="mw-redirect" title="Stack (data structure)">stack</a> of a <a href="Pushdown_automaton" title="Pushdown automaton">pushdown automaton</a>. This allows the algorithm to encode the nondeterministic choices in parsing an <a href="Ambiguous_grammar" title="Ambiguous grammar">ambiguous grammar</a>, sometimes with greater efficiency.

In the following diagram, there are four stacks: {7,3,1,0}, {7,4,1,0}, {7,5,2,0}, and {8,6,2,0}.

Another way to simulate nondeterminism would be to duplicate the stack as needed. The duplication would be less efficient since vertices would not be shared. For this example, 16 vertices would be needed instead of 9.

<div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2></div>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre>GSSnode* GSS::add(GSSnode* prev, int elem)

{

int prevlevel = prev->level;

assert(levels.size() >= prevlevel + 1);

int level = prevlevel + 1;

{

levels.resize(level + 1);

}

GSSnode* node = findElemAtLevel(level, elem);

if (node == nullptr)

{

node = new GSSnode();

node->elem = elem;

node->level = level;

levels[level].push_back(node);

}

node->add(prev);

return node;

}

</pre></div>

<div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre>void GSS::remove(GSSnode* node)

{

if (levels.size() > node->level + 1)

if (findPrevAtLevel(node->level + 1, node)) throw Exception("Can remove only from top.");

for (int i = 0; i < levels[node->level].size(); i++)

if (levels[node->level][i] == node)

{

levels[node->level].erase(levels[node->level].begin() + i);

break;

}

delete node;

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Masaru Tomita. Graph-Structured Stack And Natural Language Parsing. Annual Meeting of the Association of Computational Linguistics, 1988. <a rel="nofollow" class="external autonumber" href="http://www.aclweb.org/anthology/P88-1031">[1]</a></li>

<li>Elizabeth Scott, Adrian Johnstone GLL Parsing <a rel="nofollow" class="external text" href="http://dotat.at/tmp/gll.pdf">gll.pdf</a></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2022-03-11" href="https://en.wikipedia.org/wiki/?title=Graph-structured_stack&oldid=1076467531">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>